A vehicle driver may use a telematics unit as part of a vehicle navigation system to provide him or her with turn-by-turn directions. When the vehicle driver requests directions, the telematics unit sends a route request to a navigation server that is also part of the vehicle navigation system that contains the vehicle's current location, time-of-day, and destination. Thereafter, the vehicle navigation system provides turn-by-turn directions of the shortest route with respect to distance from the vehicle's current location to the destination. However, the shortest route with respect to distance (shortest distance route) may not be the shortest route with respect to time (shortest time route). For example, the shortest distance route may have high traffic congestion during rush hour and thus may not be the shortest time route at that time. An alternate route that may be longer with respect to distance may be shorter with respect to time. Thus, there is a need for a vehicle navigation system to be able to determine accurate travel times between two locations during a specific time-of-day to provide a vehicle driver the shortest time route when he or she requests route directions to a destination.